package leetcode.editor.cn.q0xx

import java.util.*

class Q20 {

    fun isValid(s: String): Boolean {
        if (s.isEmpty()) return true
        if (s.length % 2 != 0) return false
        val map = mapOf(')' to '(', ']' to '[', '}' to '{')
        val stack = Stack<Char>()
        for (c in s) {
            if (map.containsKey(c)) {
                if (stack.empty() || stack.pop() != map[c])
                    return false
            } else {
                stack.push(c)
            }
        }
        return stack.empty()
    }
}